home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group97a.txt / 000052_icon-group-sender _Thu Feb 27 09:59:21 1997.msg < prev    next >
Internet Message Format  |  2000-09-20  |  3KB
  1. Received: by cheltenham.cs.arizona.edu; Fri, 28 Feb 1997 08:56:42 MST
  2. To: icon-group@cs.arizona.edu
  3. Date: Thu, 27 Feb 1997 09:59:21 -0500
  4. From: Jan Galkowski <jan@solstice.digicomp.com>
  5. Message-Id: <3315A149.41C67EA6@solstice.digicomp.com>
  6. Organization: Digicomp Research Corporation
  7. Sender: icon-group-request@cs.arizona.edu
  8. References: <331437DE.41C67EA6@solstice.digicomp.com>, <5f1r3u$b7l@nef.ens.fr>
  9. Subject: Re: Icon and two-dimensional matching
  10. Errors-To: icon-group-errors@cs.arizona.edu
  11. Status: RO
  12. Content-Length: 2336
  13.  
  14. Marc Espie wrote:
  15. > 
  16. > In article <331437DE.41C67EA6@solstice.digicomp.com>,
  17. > Jan Galkowski  <jan@solstice.digicomp.com> wrote:
  18. > [SMALLER reply though]
  19. > >[LONG post warning!]
  20.  
  21. [snip]
  22.  
  23. >
  24. > Icon tables and sets are indeed a very powerful mechanism. However,
  25. > they sometimes suffer from their generality. The current implementation
  26. > uses hash functions that assume a rather smooth average distribution
  27. > of the data.
  28.  
  29. [snip]
  30.  
  31. > However, I've also ran into some spectacular failures. You see, the
  32. > sets of words I study are NOT average. Indeed, I am trying to find
  33. > some non obvious correlations between those... and the hashing functions...
  34. > well, I've got cases where everything ended up in one or two buckets,
  35. > or rather larger sets where the hashing process failed due to the
  36. > sheer size of the data.
  37. > 
  38. > I would rather like to be able to specify MORE things about my sets
  39. > (average size, distribution of data, other hashing functions) than
  40. > is possible with the current implementation.
  41.  
  42. Well, hash functions do have the drawback of making assumptions about
  43. the distribution of data.  This doesn't matter if the implementation is
  44. Icon,
  45. Perl, or APL.  (APL doesn't have a key-table lookup mechanism like
  46. Icon and Perl do, but it does use a hash function to retrieve variable 
  47. identifiers and sometimes APL programmers use a plethora of global
  48. variables to achieve the same effect.)  That's part of their nature.
  49.  
  50. > 
  51. > Right now, I have to reinvent the wheel, and reimplement somehow my
  52. > own sets without all the clarity  Icon procures to us.
  53.  
  54. Apart from the address space limitation -- which I'd think
  55. you'd overcome by defining a bigger table than you need -- I'd think the
  56. answer to the poor distribution problem would be to "prehash" the keys
  57. instead of investing in a lot of effort to build lookup routines, adding
  58. routines, removal routines, etc.  If one can tell lots of distinct keys 
  59. map into the same two buckets, use their distinctions to remap
  60. them into a wider scatter.  Why couldn't you use the Icon "map" to
  61. systematically jumble things up a bit?
  62. > 
  63.  
  64. [snip]
  65.  
  66. I'm curious: What does your post have to do with two-dimensional
  67. matching, or did it just comment on my lead paragraphs?
  68. -- 
  69.  Jan Theodore Galkowski,
  70.     Developer, tool & numerical methods elf
  71.  Digicomp Research Corporation,
  72.  Ithaca, NY 14850-5720
  73.